home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 15 / CU Amiga Magazine's Super CD-ROM 15 (1997)(EMAP Images)(GB)[!][issue 1997-10].iso / CUCD / Graphics / Ghostscript / source / gdevrun.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-05-17  |  12.4 KB  |  435 lines
  1. /* Copyright (C) 1995 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* gdevrun.c */
  20. /* Run-length encoded "device" */
  21. #include "memory_.h"
  22. #include "gx.h"
  23. #include "gserrors.h"
  24. #include "gxdevice.h"
  25. #include "gxdevmem.h"
  26.  
  27. /*
  28.  * The pseudo-device in this file stores 8-bit "pixels" with run-length
  29.  * encoding.  Since it may allocate less space than is required to
  30.  * store all possible values, it may have to discard some update requests.
  31.  */
  32.  
  33. /*
  34.  * Define the representation of each run.  We store runs in a doubly-
  35.  * linked list using the old trick of storing only a single pointer which
  36.  * is the xor of the successor and predecessor indices.
  37.  * Run 0 is a dummy end-of-line run; run 1 is a dummy start-of-line run.
  38.  * The dummy runs have length 255 to prevent merging.
  39.  */
  40. typedef byte run_length;
  41. typedef byte run_value;
  42. typedef ushort run_index;
  43. typedef struct run_s {
  44.     run_length length;
  45.     run_value value;
  46.     run_index nix;    /* for allocated runs, xor of successor and */
  47.             /* predecessor indices; for free runs, */
  48.             /* index of next free run */
  49. } run;
  50. /*
  51.  * Define a pointer into a run list.  The xor trick requires that we
  52.  * store both the current index and the next (or previous) one.
  53.  * For speed, we keep both the index of and the pointer to the current run.
  54.  */
  55. typedef struct run_ptr_s {
  56.     run *ptr;
  57.     run_index index;    /* index of current run */
  58.     run_index next;        /* index of next run */
  59. } run_ptr;
  60. typedef struct const_run_ptr_s {
  61.     const run *ptr;
  62.     run_index index;    /* index of current run */
  63.     run_index next;    /* index of next run */
  64. } const_run_ptr;
  65. /* Accessors */
  66. #define rp_length(rp) ((rp).ptr->length)
  67. #define rp_value(rp) ((rp).ptr->value)
  68. #define rp_nix(rp) ((rp).ptr->nix)
  69. /* Traversers */
  70. #define rp_at_start(rp) ((rp).index == 1)
  71. #define rp_at_end(rp) ((rp).index == 0)
  72. #define rp_start(rp, data)\
  73.   ((rp).index = (data)[1].nix,\
  74.    (rp).ptr = (data) + (rp).index,\
  75.    (rp).next = rp_nix(rp) ^ 1)
  76. /* Note that rp_next and rp_prev allow rpn == rpc. */
  77. #define rp_next(rpc, data, rpn, itemp)\
  78.   (itemp = (rpc).index,\
  79.    (rpn).ptr = (data) + ((rpn).index = (rpc).next),\
  80.    (rpn).next = itemp ^ rp_nix(rpn))
  81. #define rp_prev(rpc, data, rpp, itemp)\
  82.   (itemp = (rpc).next ^ rp_nix(rpc),\
  83.    (rpp).next = (rpc).index,\
  84.    (rpp).ptr = (data) + ((rpp).index = itemp))
  85. /* Insert/delete */
  86. #define rp_delete_next(rpc, data, line, rpn, rpn2, itemp)\
  87.   (rp_next(rpc, data, rpn, itemp),\
  88.    rp_next(rpn, data, rpn2, itemp),\
  89.    rp_nix(rpc) ^= (rpn).index ^ (rpn2).index,\
  90.    rp_nix(rpn2) ^= (rpn).index ^ (rpc).index,\
  91.    rp_nix(rpn) = (line)->free,\
  92.    (line)->free = (rpn).index)
  93. #define rp_insert_next(rpc, data, line, rpn, itemp)\
  94.   (rp_next(rpc, data, rpn, itemp),\
  95.    itemp = (line)->free,\
  96.    rp_nix(rpc) ^= (rpn).index ^ itemp,\
  97.    rp_nix(rpn) ^= (rpc).index ^ itemp,\
  98.    (rpn).next = (rpn).index,\
  99.    (rpn).index = itemp,\
  100.    (rpn).ptr = (data) + itemp,\
  101.    (line)->free = rp_nix(rpn),\
  102.    rp_nix(rpn) = (rpc).index ^ (rpn).next)
  103. #define rp_insert_prev(rpc, data, line, rpp, itemp)\
  104.   (rp_prev(rpc, data, rpp, itemp),\
  105.    itemp = (line)->free,\
  106.    rp_nix(rpc) ^= (rpp).index ^ itemp,\
  107.    rp_nix(rpp) ^= (rpc).index ^ itemp,\
  108.    (rpp).ptr = (data) + itemp,\
  109.    rp_nix(rpp) = (rpp).index ^ (rpc).index,\
  110.    (rpp).index = itemp,\
  111.    (line)->free = rp_nix(rpp))
  112.  
  113. /*
  114.  * Define the state of a single scan line.
  115.  *
  116.  * We maintain the following invariant: if two adjacent runs have the
  117.  * same value, the sum of their lengths is at least 256.  This may miss
  118.  * optimality by nearly a factor of 2, but it's far easier to maintain
  119.  * than a true optimal representation.
  120.  *
  121.  * For speed in the common case where nothing other than 0 is ever stored,
  122.  * we initially don't bother to construct the runs (or the free run list)
  123.  * for a line at all.
  124.  */
  125. typedef struct run_line_s {
  126.     run *data;    /* base of runs */
  127.     int zero;    /* 0 if line not initialized, -1 if initialized */
  128.     uint xcur;    /* x value at cursor position */
  129.     run_ptr rpcur;    /* cursor */
  130.     run_index free;    /* head of free list */
  131. } run_line;
  132.  
  133. /*
  134.  * Define the device, built on an 8-bit memory device.
  135.  */
  136. typedef struct gx_device_run_s {
  137.     gx_device_memory md;
  138.     uint runs_per_line;
  139.     run_line *lines;
  140.     int umin, umax1;    /* some range of uninitialized lines */
  141. } gx_device_run;
  142.  
  143. #define rdev ((gx_device_run *)dev)
  144.  
  145. /* Open the device. */
  146. private int
  147. run_open(gx_device *dev)
  148. {    run_line *line = rdev->lines;
  149.     run *data = (run *)rdev->md.base;
  150.     int i;
  151.  
  152.     /*
  153.      * We need ceil(width / 255) runs to represent a line where all
  154.      * elements have the same value, +2 for the start and end runs,
  155.      * +2 for the check for 2 free runs when doing a replacement.
  156.      */
  157.     if ( rdev->runs_per_line < (dev->width + 254) / 255 + 4 )
  158.       return_error(gs_error_rangecheck);
  159.     for ( i = 0; i < dev->height; ++line, data += rdev->runs_per_line, ++i )
  160.     {    line->data = data;
  161.         line->zero = 0;
  162.     }
  163.     rdev->umin = 0;
  164.     rdev->umax1 = dev->height;
  165.     return 0;
  166. }
  167.  
  168. /* Finish initializing a line.  This is a separate procedure only */
  169. /* for readability. */
  170. private void
  171. run_line_initialize(gx_device *dev, int y)
  172. {    run_line *line = &rdev->lines[y];
  173.     run *data = line->data;
  174.     int left = dev->width;
  175.     run_index index = 2;
  176.     run *rcur;
  177.  
  178.     line->zero = -1;
  179.     data[0].length = 255;        /* see above */
  180.     data[0].value = 0;        /* shouldn't matter */
  181.     data[1].length = 255;
  182.     data[1].value = 0;
  183.     data[1].nix = 2;
  184.     rcur = data + index;
  185.     for ( ; left > 0; index++, rcur++, left -= 255 )
  186.     {    rcur->length = min(left, 255);
  187.         rcur->value = 0;
  188.         rcur->nix = (index - 1) ^ (index + 1);
  189.     }
  190.     rcur->nix = index - 2;
  191.     data[0].nix = index - 1;
  192.     line->xcur = 0;
  193.     line->rpcur.ptr = data + 2;
  194.     line->rpcur.index = 2;
  195.     line->rpcur.next = data[2].nix ^ 1;
  196.     line->free = index;
  197.     for ( ; index < rdev->runs_per_line; ++index )
  198.       data[index].nix = index + 1;
  199.     data[index - 1].nix = 0;
  200.     if ( y >= rdev->umin && y < rdev->umax1 )
  201.     {    if ( y > (rdev->umin + rdev->umax1) >> 1 )
  202.           rdev->umax1 = y;
  203.         else
  204.           rdev->umin = y + 1;
  205.     }
  206. }
  207.  
  208. /* Replace an interval of a line with a new value.  This is the procedure */
  209. /* that does all the interesting work.  We assume the line has been */
  210. /* initialized, and that 0 <= xo < xe <= dev->width. */
  211. private int
  212. run_fill_interval(run_line *line, int xo, int xe, run_value new)
  213. {    run *data = line->data;
  214.     int xc = line->xcur;
  215.     run_ptr rpc;
  216.     run_index itemp;
  217.     int x0, x1;
  218.     run_ptr rp0;
  219.  
  220.     rpc = line->rpcur;
  221.  
  222.     /* Find the run that contains xo. */
  223.  
  224.     if ( xo < xc )
  225.       { while ( xo < xc )
  226.           rp_prev(rpc, data, rpc, itemp), xc -= rp_length(rpc);
  227.       }
  228.     else
  229.       { while ( xo >= xc + rp_length(rpc) )
  230.           xc += rp_length(rpc), rp_next(rpc, data, rpc, itemp);
  231.       }
  232.  
  233.     /*
  234.      * Skip runs above xo that already contain the new value.
  235.      * If the entire interval already has the correct value, exit.
  236.      * If we skip any such runs, set xo to just above them.
  237.      */
  238.  
  239.     for ( ; !rp_at_end(rpc) && rp_value(rpc) == new;
  240.           rp_next(rpc, data, rpc, itemp)
  241.         )
  242.       if ( (xo = xc += rp_length(rpc)) >= xe )
  243.         return 0;
  244.     x0 = xc, rp0 = rpc;
  245.  
  246.     /* Find the run that contains xe-1. */
  247.  
  248.     while ( xe > xc + rp_length(rpc) )
  249.       xc += rp_length(rpc), rp_next(rpc, data, rpc, itemp);
  250.  
  251.     /*
  252.      * Skip runs below xe that already contain the new value.
  253.      * (We know that some run between xo and xe doesn't.)
  254.      * If we skip any such runs, set xe to just below them.
  255.      */
  256.  
  257.     while ( rp_prev(rpc, data, rpc, itemp), rp_value(rpc) == new )
  258.       xe = xc -= rp_length(rpc);
  259.     rp_next(rpc, data, rpc, itemp);
  260.  
  261.     /*
  262.      * At this point, we know the following:
  263.      *    x0 <= xo < x0 + rp_length(rp0).
  264.      *    rp_value(rp0) != new.
  265.      *    xc <= xe-1 < xc + rp_length(rpc).
  266.      *    rp_value(rpc) != new.
  267.      * Note that rp0 and rpc may point to the same run.
  268.      */
  269.  
  270.     /*
  271.      * Check that we have enough free runs to do the replacement.
  272.      * In the worst case, where we have to split existing runs
  273.      * at both ends of the interval, two new runs are required.
  274.      * We just check for having at least two free runs, since this
  275.      * is simple and wastes at most 2 runs.
  276.      */
  277.  
  278.     if ( line->free == 0 || data[line->free].nix == 0 )
  279.       return_error(-1);
  280.  
  281.     /* Split off any unaffected prefix of the run at rp0. */
  282.  
  283.     if ( x0 < xo )
  284.     {    uint diff = xo - x0;
  285.         run_value v0 = rp_value(rp0);
  286.         run_ptr rpp;
  287.  
  288.         rp_prev(rp0, data, rpp, itemp);
  289.         if ( rp_value(rpp) == v0 && rp_length(rpp) + diff <= 255 )
  290.           rp_length(rpp) += diff;
  291.         else
  292.           { rp_insert_prev(rp0, data, line, rpp, itemp);
  293.             rp_length(rpp) = diff;
  294.             rp_value(rpp) = v0;
  295.           }
  296.     }
  297.  
  298.     /* Split off any unaffected suffix of the run at rpc. */
  299.  
  300.     x1 = xc + rp_length(rpc);
  301.     if ( x1 > xe )
  302.     {    uint diff = x1 - xe;
  303.         run_value vc = rp_value(rpc);
  304.         run_ptr rpn;
  305.  
  306.         rp_next(rpc, data, rpn, itemp);
  307.         if ( rp_value(rpn) == vc && rp_length(rpn) + diff <= 255 )
  308.           rp_length(rpn) += diff;
  309.         else
  310.           { rp_insert_next(rpc, data, line, rpn, itemp);
  311.             rp_length(rpn) = diff;
  312.             rp_value(rpn) = vc;
  313.           }
  314.     }
  315.  
  316.     /* Delete all runs from rp0 through rpc. */
  317.  
  318.     rp_prev(rp0, data, rp0, itemp);
  319.     {    run_ptr rpn, rpn2;
  320.         while ( rp0.next != rpc.next )
  321.           rp_delete_next(rp0, data, line, rpn, rpn2, itemp);
  322.     }
  323.  
  324.     /*
  325.      * Finally, insert new runs with the new value.
  326.      * We need to check for one boundary case, namely,
  327.      * xo == x0 and the next lower run has the new value.
  328.      * (There's probably a way to structure the code just slightly
  329.      * differently to avoid this test.)
  330.      */
  331.  
  332.     {    uint left = xe - xo;
  333.         if ( xo == x0 && rp_value(rp0) == new &&
  334.              rp_length(rp0) + left <= 255
  335.            )
  336.           rp_length(rp0) += left;
  337.         else
  338.         { /*
  339.            * If we need more than one run, we probably should
  340.            * divide up the length to create more runs with length
  341.            * less than 255 in order to improve the chances of
  342.            * a later merge, but we won't bother right now.
  343.            */
  344.           do
  345.             {    run_ptr rpn;
  346.             rp_insert_next(rp0, data, line, rpn, itemp);
  347.             rp_length(rpn) = min(left, 255);
  348.             rp_value(rpn) = new;
  349.             }
  350.           while ( (left -= 255) > 0 );
  351.         }
  352.     }
  353.  
  354.     return 0;
  355. }
  356.  
  357. /* Replace a rectangle with a new value. */
  358. private int
  359. run_fill_rectangle(gx_device *dev, int x, int y, int w, int h,
  360.   gx_color_index color)
  361. {    int xe;
  362.     run_line *line;
  363.     int ny;
  364.  
  365.     fit_fill(dev, x, y, w, h);
  366.     /*
  367.      * If the new value is 0 and the rectangle falls entirely within
  368.      * the uninitialized region that we're keeping track of,
  369.      * we can skip the entire operation.
  370.      */
  371.     if ( (byte)color == 0 && y >= rdev->umin && y + h <= rdev->umax1 )
  372.       return 0;
  373.  
  374.     xe = x + w;
  375.     for ( line = &rdev->lines[y], ny = h; ny > 0; ++line, --ny )
  376.       if ( (byte)color != line->zero )
  377.         { if ( line->zero == 0 )
  378.         run_line_initialize(dev, y + h - ny);
  379.           run_fill_interval(line, x, xe, (byte)color);
  380.         }
  381.     return 0;
  382. }
  383.  
  384. /* Get a fully expanded scan line. */
  385. private int
  386. run_get_bits(gx_device *dev, int y, byte *row, byte **actual_row)
  387. {    const run_line *line = &rdev->lines[y];
  388.     const run *data = line->data;
  389.     const_run_ptr rp;
  390.     byte *q = *actual_row = row;
  391.     run_index itemp;
  392.  
  393.     if ( line->zero == 0 )
  394.     {    memset(row, 0, dev->width);
  395.         return 0;
  396.     }
  397.     for ( rp_start(rp, data); !rp_at_end(rp);
  398.           rp_next(rp, data, rp, itemp)
  399.         )
  400.     { memset(q, rp_value(rp), rp_length(rp));
  401.       q += rp_length(rp);
  402.     }
  403.     return 0;
  404. }
  405.  
  406. /* Debugging code */
  407.  
  408. #ifdef DEBUG
  409.  
  410. void
  411. debug_print_run(const run *data, run_index index, const char *prefix)
  412. {    const run *pr = data + index;
  413.     dprintf5("%s%5d: length = %3d, value = %3d, nix = %5u\n",
  414.          prefix, index, pr->length, pr->value, pr->nix);
  415. }
  416.  
  417. void
  418. debug_print_run_line(const run_line *line, const char *prefix)
  419. {    const run *data = line->data;
  420.     dprintf5("%sruns at 0x%lx: zero = %d, free = %u, xcur = %u,\n",
  421.         prefix, (ulong)data, line->zero, line->free, line->xcur);
  422.     dprintf4("%s  rpcur = {ptr = 0x%lx, index = %u, next = %u}\n",
  423.         prefix, (ulong)line->rpcur.ptr, line->rpcur.index, line->rpcur.next);
  424.     { const_run_ptr rpc;
  425.       uint itemp;
  426.       rp_start(rpc, data);
  427.       while ( !rp_at_end(rpc) )
  428.         { debug_print_run(data, rpc.index, prefix);
  429.           rp_next(rpc, data, rpc, itemp);
  430.         }
  431.     }
  432. }
  433.  
  434. #endif                    /* DEBUG */
  435.